/*
 * %W% %E%
 *
 * Copyright (c) 2006, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

package java.util;

/**
 * Linked list implementation of the <tt>List</tt> interface. Implements all
 * optional list operations, and permits all elements (including <tt>null</tt>).
 * In addition to implementing the <tt>List</tt> interface, the
 * <tt>LinkedList</tt> class provides uniformly named methods to <tt>get</tt>,
 * <tt>remove</tt> and <tt>insert</tt> an element at the beginning and end of
 * the list. These operations allow linked lists to be used as a stack,
 * {@linkplain Queue queue}, or {@linkplain Deque double-ended queue}.
 * <p>
 * 
 * The class implements the <tt>Deque</tt> interface, providing
 * first-in-first-out queue operations for <tt>add</tt>, <tt>poll</tt>, along
 * with other stack and deque operations.
 * <p>
 * 
 * All of the operations perform as could be expected for a doubly-linked list.
 * Operations that index into the list will traverse the list from the beginning
 * or the end, whichever is closer to the specified index.
 * <p>
 * 
 * <p>
 * <strong>Note that this implementation is not synchronized.</strong> If
 * multiple threads access a linked list concurrently, and at least one of the
 * threads modifies the list structurally, it <i>must</i> be synchronized
 * externally. (A structural modification is any operation that adds or deletes
 * one or more elements; merely setting the value of an element is not a
 * structural modification.) This is typically accomplished by synchronizing on
 * some object that naturally encapsulates the list.
 * 
 * If no such object exists, the list should be "wrapped" using the
 * {@link Collections#synchronizedList Collections.synchronizedList} method.
 * This is best done at creation time, to prevent accidental unsynchronized
 * access to the list:
 * 
 * <pre>
 *   List list = Collections.synchronizedList(new LinkedList(...));
 * </pre>
 * 
 * <p>
 * The iterators returned by this class's <tt>iterator</tt> and
 * <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
 * structurally modified at any time after the iterator is created, in any way
 * except through the Iterator's own <tt>remove</tt> or <tt>add</tt> methods,
 * the iterator will throw a {@link ConcurrentModificationException}. Thus, in
 * the face of concurrent modification, the iterator fails quickly and cleanly,
 * rather than risking arbitrary, non-deterministic behavior at an undetermined
 * time in the future.
 * 
 * <p>
 * Note that the fail-fast behavior of an iterator cannot be guaranteed as it
 * is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification. Fail-fast iterators throw
 * <tt>ConcurrentModificationException</tt> on a best-effort basis. Therefore,
 * it would be wrong to write a program that depended on this exception for its
 * correctness: <i>the fail-fast behavior of iterators should be used only to
 * detect bugs.</i>
 * 
 * <p>
 * This class is a member of the <a href="{@docRoot}
 * /../technotes/guides/collections/index.html"> Java Collections Framework</a>.
 * 
 * @author Josh Bloch
 * @version %I%, %G%
 * @see List
 * @see ArrayList
 * @see o
 * @since 1.2
 * @param <E>
 *            the type of elements held in this collection
 */

/*
 * LinkedList也和ArrayList一样实现了List接口，但是它执行插入和删除操作时比ArrayList更加高效，因为它是基于链表的。
 * 基于链表也决定了它在随机访问方面要比ArrayList逊色一点。
 * 除此之外，LinkedList还提供了一些可以使其作为栈、队列、双端队列的方法。这些方法中有些彼此之间只是名称的区别，
 * 以使得这些名字在特定的上下文中显得更加的合适。
 * 
 * LinkedList继承自AbstractSequenceList、实现了List及Deque接口。
 * 其实AbstractSequenceList已经实现了List接口，这里标注出List只是更加清晰而已。
 * AbstractSequenceList提供了List接口骨干性的实现以减少实现List接口的复杂度。Deque接口定义了双端队列的操作
 * 
 * LinkedList 双向循环链表
 */
public class LinkedList<E> extends AbstractSequentialList<E> implements
		List<E>, Deque<E>, Cloneable, java.io.Serializable {

	// size肯定就是LinkedList对象里面存储的元素个数了。LinkedList既然是基于链表实现的，
	// 那么这个header肯定就是链表的头结点了，Entry就是节点对象了
	private transient Entry<E> header = new Entry<E>(null, null, null);
	private transient int size = 0;

	/**
	 * Constructs an empty list.
	 */

	/*
	 * LinkedList提供了两个构造方法。第一个构造方法不接受参数，
	 * 只是将header节点的前一节点和后一节点都设置为自身（注意，这个是一个双向循环链表
	 * ，如果不是循环链表，空链表的情况应该是header节点的前一节点和后一节点均为null），
	 * 这样整个链表其实就只有header一个节点，用于表示一个空的链表。第二个构造方法接收一个Collection参数c，
	 * 调用第一个构造方法构造一个空的链表，之后通过addAll将c中的元素全部添加到链表中。
	 */
	public LinkedList() {
		header.next = header.previous = header;
	}

	/**
	 * Constructs a list containing the elements of the specified collection, in
	 * the order they are returned by the collection's iterator.
	 * 
	 * @param c
	 *            the collection whose elements are to be placed into this list
	 * @throws NullPointerException
	 *             if the specified collection is null
	 */
	public LinkedList(Collection<? extends E> c) {
		this();
		addAll(c);
	}

	/**
	 * Returns the first element in this list.
	 * 
	 * @return the first element in this list
	 * @throws NoSuchElementException
	 *             if this list is empty
	 */
	public E getFirst() {
		if (size == 0)
			throw new NoSuchElementException();

		return header.next.element;
	}

	/**
	 * Returns the last element in this list.
	 * 
	 * @return the last element in this list
	 * @throws NoSuchElementException
	 *             if this list is empty
	 */

	// getLast()方法和getFirst()方法类似，只是获取的是header节点的前一个节点的元素。因为是循环链表，
	// 所以header节点的前一节点就是链表的最后一个节点。
	public E getLast() {
		if (size == 0)
			throw new NoSuchElementException();

		return header.previous.element;
	}

	/**
	 * Removes and returns the first element from this list.
	 * 
	 * @return the first element from this list
	 * @throws NoSuchElementException
	 *             if this list is empty
	 */
	public E removeFirst() {
		return remove(header.next);
	}

	/**
	 * Removes and returns the last element from this list.
	 * 
	 * @return the last element from this list
	 * @throws NoSuchElementException
	 *             if this list is empty
	 */
	public E removeLast() {
		return remove(header.previous);
	}

	/**
	 * Inserts the specified element at the beginning of this list.
	 * 
	 * @param e
	 *            the element to add
	 */

	/*
	 * 结合addBefore(E e,Entry<E> entry)方法，很容易理解addFrist(E
	 * e)只需实现在header元素的下一个元素之前插入， addLast(E
	 * e)只需在实现在header节点前（因为是循环链表，所以header的前一个节点就是链表的最后一个节点）插入节点（插入后在2号节点之后）。
	 */

	// // 双向循环链表 head <=> e <=> ... <=>head
	public void addFirst(E e) {
		addBefore(e, header.next);
	}

	/**
	 * Appends the specified element to the end of this list.
	 * 
	 * <p>
	 * This method is equivalent to {@link #add}.
	 * 
	 * @param e
	 *            the element to add
	 */
	// 双向循环链表 head <=> ... <=> e <=> head
	public void addLast(E e) {
		addBefore(e, header); // <=== =add(E e)
	}

	/**
	 * Returns <tt>true</tt> if this list contains the specified element. More
	 * formally, returns <tt>true</tt> if and only if this list contains at
	 * least one element <tt>e</tt> such that
	 * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
	 * 
	 * @param o
	 *            element whose presence in this list is to be tested
	 * @return <tt>true</tt> if this list contains the specified element
	 */
	// contains(Object o)方法通过判断indexOf(Object o)方法返回的值是否是-1来判断链表中是否包含对象o。
	public boolean contains(Object o) {
		return indexOf(o) != -1;
	}

	/**
	 * Returns the number of elements in this list.
	 * 
	 * @return the number of elements in this list
	 */
	public int size() {
		return size;
	}

	/**
	 * Appends the specified element to the end of this list.
	 * 
	 * <p>
	 * This method is equivalent to {@link #addLast}.
	 * 
	 * @param e
	 *            element to be appended to this list
	 * @return <tt>true</tt> (as specified by {@link Collection#add})
	 */
	// 从代码可以看出，add(E e)方法只是调用了addBefore(E e,Entry<E> entry)方法，并且返回true。
	// 双向循环链表 head <=> ...<=> e <=> head
	public boolean add(E e) {
		addBefore(e, header);
		return true;
	}

	/**
	 * Removes the first occurrence of the specified element from this list, if
	 * it is present. If this list does not contain the element, it is
	 * unchanged. More formally, removes the element with the lowest index
	 * <tt>i</tt> such that
	 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
	 * (if such an element exists). Returns <tt>true</tt> if this list contained
	 * the specified element (or equivalently, if this list changed as a result
	 * of the call).
	 * 
	 * @param o
	 *            element to be removed from this list, if present
	 * @return <tt>true</tt> if this list contained the specified element
	 */
	public boolean remove(Object o) {
		if (o == null) {
			for (Entry<E> e = header.next; e != header; e = e.next) {
				if (e.element == null) {
					remove(e);
					return true;
				}
			}
		} else {
			for (Entry<E> e = header.next; e != header; e = e.next) {
				if (o.equals(e.element)) {
					remove(e);
					return true;
				}
			}
		}
		return false;
	}

	/**
	 * Appends all of the elements in the specified collection to the end of
	 * this list, in the order that they are returned by the specified
	 * collection's iterator. The behavior of this operation is undefined if the
	 * specified collection is modified while the operation is in progress.
	 * (Note that this will occur if the specified collection is this list, and
	 * it's nonempty.)
	 * 
	 * @param c
	 *            collection containing elements to be added to this list
	 * @return <tt>true</tt> if this list changed as a result of the call
	 * @throws NullPointerException
	 *             if the specified collection is null
	 */
	public boolean addAll(Collection<? extends E> c) {
		return addAll(size, c);
	}

	/**
	 * Inserts all of the elements in the specified collection into this list,
	 * starting at the specified position. Shifts the element currently at that
	 * position (if any) and any subsequent elements to the right (increases
	 * their indices). The new elements will appear in the list in the order
	 * that they are returned by the specified collection's iterator.
	 * 
	 * @param index
	 *            index at which to insert the first element from the specified
	 *            collection
	 * @param c
	 *            collection containing elements to be added to this list
	 * @return <tt>true</tt> if this list changed as a result of the call
	 * @throws IndexOutOfBoundsException
	 *             {@inheritDoc}
	 * @throws NullPointerException
	 *             if the specified collection is null
	 */
	// 构造方法中的调用了addAll(Collection<? extends E> c)方法，
	// 而在addAll(Collection<? extends E> c)方法中仅仅是将size当做index参数调用了
	// addAll(int index,Collection<? extends E> c)方法。
	// // index参数指定collection中插入的第一个元素的位置
	public boolean addAll(int index, Collection<? extends E> c) {

		// // 插入位置超过了链表的长度或小于0，报IndexOutOfBoundsException异常
		if (index < 0 || index > size)
			throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
					+ size);
		Object[] a = c.toArray();
		int numNew = a.length;
		// 若需要插入的节点个数为0则返回false，表示没有插入元素
		if (numNew == 0)
			return false;
		modCount++;

		// 保存index处的节点。插入位置如果是size，则在头结点前面插入，否则获取index处的节点
		Entry<E> successor = (index == size ? header : entry(index));
		// 获取前一个节点，插入时需要修改这个节点的next引用
		Entry<E> predecessor = successor.previous;
		// 按顺序将a数组中的第一个元素插入到index处，将之后的元素插在这个元素后面
		for (int i = 0; i < numNew; i++) {
			// 结合Entry的构造方法，这条语句是插入操作，相当于C语言中链表中插入节点并修改指针
			Entry<E> e = new Entry<E>((E) a[i], successor, predecessor);
			// 插入节点后将前一节点的next指向当前节点，相当于修改前一节点的next指针
			predecessor.next = e;
			// 相当于C语言中成功插入元素后将指针向后移动一个位置以实现循环的功能
			predecessor = e;
		}
		// 插入元素前index处的元素链接到插入的Collection的最后一个节点
		successor.previous = predecessor;

		// 修改size
		size += numNew;
		return true;
	}

	/**
	 * Removes all of the elements from this list.
	 */
	public void clear() {
		// e可以理解为一个移动的“指针”，因为是循环链表，所以回到header的时候说明已经没有节点了
		Entry<E> e = header.next;
		while (e != header) {
			// 保留e的下一个节点的引用
			Entry<E> next = e.next;
			// 接触节点e对前后节点的引用
			e.next = e.previous = null;
			// 将节点e的内容置空
			e.element = null;
			// 将e移动到下一个节点
			e = next;
		}
		// 将header构造成一个循环链表，同构造方法构造一个空的LinkedList
		header.next = header.previous = header;
		// 修改size
		size = 0;
		modCount++;
	}

	// Positional Access Operations

	/**
	 * Returns the element at the specified position in this list.
	 * 
	 * @param index
	 *            index of the element to return
	 * @return the element at the specified position in this list
	 * @throws IndexOutOfBoundsException
	 *             {@inheritDoc}
	 */
	// get(int index)方法用于获得指定索引位置的节点的元素。它通过entry(int index)方法获取节点。entry(int
	// index)方法遍历链表并获取节点
	public E get(int index) {
		return entry(index).element;
	}

	/**
	 * Replaces the element at the specified position in this list with the
	 * specified element.
	 * 
	 * @param index
	 *            index of the element to replace
	 * @param element
	 *            element to be stored at the specified position
	 * @return the element previously at the specified position
	 * @throws IndexOutOfBoundsException
	 *             {@inheritDoc}
	 */

	// 先获取指定索引的节点，之后保留原来的元素，然后用element进行替换，之后返回原来的元素。
	public E set(int index, E element) {
		Entry<E> e = entry(index);
		E oldVal = e.element;
		e.element = element;
		return oldVal;
	}

	/**
	 * Inserts the specified element at the specified position in this list.
	 * Shifts the element currently at that position (if any) and any subsequent
	 * elements to the right (adds one to their indices).
	 * 
	 * @param index
	 *            index at which the specified element is to be inserted
	 * @param element
	 *            element to be inserted
	 * @throws IndexOutOfBoundsException
	 *             {@inheritDoc}
	 */

	// 也是调用了addBefore(E e,Entry<E> entry)方法，只是entry节点由index的值决定。
	public void add(int index, E element) {
		addBefore(element, (index == size ? header : entry(index)));
	}

	/**
	 * Removes the element at the specified position in this list. Shifts any
	 * subsequent elements to the left (subtracts one from their indices).
	 * Returns the element that was removed from the list.
	 * 
	 * @param index
	 *            the index of the element to be removed
	 * @return the element previously at the specified position
	 * @throws IndexOutOfBoundsException
	 *             {@inheritDoc}
	 */
	public E remove(int index) {
		return remove(entry(index));
	}

	/**
	 * Returns the indexed entry.
	 */
	private Entry<E> entry(int index) {
		if (index < 0 || index >= size)
			throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
					+ size);
		Entry<E> e = header; // <==head开始遍历
		// 根据这个判断决定从哪个方向遍历这个链表 。折半，一半之前从前往后，一半之后从后往前
		if (index < (size >> 1)) {
			for (int i = 0; i <= index; i++)
				e = e.next;
		} else {
			// 可以通过header节点向前遍历，说明这个一个循环双向链表，header的previous指向链表的最后一个节点，
			// 这也验证了构造方法中对于header节点的前后节点均指向自己的解释
			for (int i = size; i > index; i--)
				e = e.previous;
		}
		return e;
	}

	// Search Operations

	/**
	 * Returns the index of the first occurrence of the specified element in
	 * this list, or -1 if this list does not contain the element. More
	 * formally, returns the lowest index <tt>i</tt> such that
	 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
	 * or -1 if there is no such index.
	 * 
	 * @param o
	 *            element to search for
	 * @return the index of the first occurrence of the specified element in
	 *         this list, or -1 if this list does not contain the element
	 */

	// ndexOf(Object o)判断o链表中是否存在节点的element和o相等，若相等则返回该节点在链表中的索引位置，若不存在则放回-1。
	public int indexOf(Object o) {
		int index = 0;
		if (o == null) {
			for (Entry e = header.next; e != header; e = e.next) {
				if (e.element == null)
					return index;
				index++;
			}
		} else {
			for (Entry e = header.next; e != header; e = e.next) {
				if (o.equals(e.element))
					return index;
				index++;
			}
		}
		return -1;
	}

	/**
	 * Returns the index of the last occurrence of the specified element in this
	 * list, or -1 if this list does not contain the element. More formally,
	 * returns the highest index <tt>i</tt> such that
	 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
	 * or -1 if there is no such index.
	 * 
	 * @param o
	 *            element to search for
	 * @return the index of the last occurrence of the specified element in this
	 *         list, or -1 if this list does not contain the element
	 */
	/*
	 * 因为查找的是last index，即最后一次出现的位置，所以采用由后向前的遍历方式。因为采用了有后向前的遍历，
	 * 所以index被赋值为size，并且循环体内执行时都进行减操作。分两种情况判断是否存在，分别是null和不为空。
	 */
	public int lastIndexOf(Object o) {
		int index = size;
		if (o == null) {
			for (Entry e = header.previous; e != header; e = e.previous) {
				index--;
				if (e.element == null)
					return index;
			}
		} else {
			for (Entry e = header.previous; e != header; e = e.previous) {
				index--;
				if (o.equals(e.element))
					return index;
			}
		}
		return -1;
	}

	// Queue operations.

	/**
	 * Retrieves, but does not remove, the head (first element) of this list.
	 * 
	 * @return the head of this list, or <tt>null</tt> if this list is empty
	 * @since 1.5
	 */
	public E peek() {
		if (size == 0)
			return null;
		return getFirst();
	}

	/**
	 * Retrieves, but does not remove, the head (first element) of this list.
	 * 
	 * @return the head of this list
	 * @throws NoSuchElementException
	 *             if this list is empty
	 * @since 1.5
	 */

	// element()方法调用了getFirst()返回链表的第一个节点的元素。为什么要提供功能一样的两个方法，
	// 像是包装了一下名字？其实这只是为了在不同的上下文“语境”中能通过更贴切的方法名调用罢了。
	public E element() {
		return getFirst();
	}

	/**
	 * Retrieves and removes the head (first element) of this list
	 * 
	 * @return the head of this list, or <tt>null</tt> if this list is empty
	 * @since 1.5
	 */
	public E poll() {
		if (size == 0)
			return null;
		return removeFirst();
	}

	// poll() pollFirst() pollLast() poll相关的方法都是获取并移除某个元素。都是和remove操作相关
	/**
	 * Retrieves and removes the head (first element) of this list.
	 * 
	 * @return the head of this list
	 * @throws NoSuchElementException
	 *             if this list is empty
	 * @since 1.5
	 */
	public E remove() {
		return removeFirst();
	}

	/**
	 * Adds the specified element as the tail (last element) of this list.
	 * 
	 * @param e
	 *            the element to add
	 * @return <tt>true</tt> (as specified by {@link Queue#offer})
	 * @since 1.5
	 */
	// 在链表尾部插入元素。
	public boolean offer(E e) {
		return add(e); // <=== =add(E e)
	}

	// Deque operations
	/**
	 * Inserts the specified element at the front of this list.
	 * 
	 * @param e
	 *            the element to insert
	 * @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
	 * @since 1.6
	 */
	// 在链表开头插入元素。
	public boolean offerFirst(E e) {
		addFirst(e);
		return true;
	}

	/**
	 * Inserts the specified element at the end of this list.
	 * 
	 * @param e
	 *            the element to insert
	 * @return <tt>true</tt> (as specified by {@link Deque#offerLast})
	 * @since 1.6
	 */
	// 在链表末尾插入元素。
	public boolean offerLast(E e) {
		addLast(e);
		return true;
	}

	// 上面这三个方法都只是调用了相应的add方法，同样只是提供了不同的方法名在不同的语境下使用。
	/**
	 * Retrieves, but does not remove, the first element of this list, or
	 * returns <tt>null</tt> if this list is empty.
	 * 
	 * @return the first element of this list, or <tt>null</tt> if this list is
	 *         empty
	 * @since 1.6
	 */
	public E peekFirst() {
		if (size == 0)
			return null;
		return getFirst();
	}

	/**
	 * Retrieves, but does not remove, the last element of this list, or returns
	 * <tt>null</tt> if this list is empty.
	 * 
	 * @return the last element of this list, or <tt>null</tt> if this list is
	 *         empty
	 * @since 1.6
	 */
	public E peekLast() {
		if (size == 0)
			return null;
		return getLast();
	}

	// peek() peekFirst() peekLast() 上面的三个方法也很简单，只是调用了对应的get方法。

	/**
	 * Retrieves and removes the first element of this list, or returns
	 * <tt>null</tt> if this list is empty.
	 * 
	 * @return the first element of this list, or <tt>null</tt> if this list is
	 *         empty
	 * @since 1.6
	 */
	public E pollFirst() {
		if (size == 0)
			return null;
		return removeFirst();
	}

	/**
	 * Retrieves and removes the last element of this list, or returns
	 * <tt>null</tt> if this list is empty.
	 * 
	 * @return the last element of this list, or <tt>null</tt> if this list is
	 *         empty
	 * @since 1.6
	 */
	public E pollLast() {
		if (size == 0)
			return null;
		return removeLast();
	}

	/**
	 * Pushes an element onto the stack represented by this list. In other
	 * words, inserts the element at the front of this list.
	 * 
	 * <p>
	 * This method is equivalent to {@link #addFirst}.
	 * 
	 * @param e
	 *            the element to push
	 * @since 1.6
	 */
	public void push(E e) {
		addFirst(e);
	}

	/**
	 * Pops an element from the stack represented by this list. In other words,
	 * removes and returns the first element of this list.
	 * 
	 * <p>
	 * This method is equivalent to {@link #removeFirst()}.
	 * 
	 * @return the element at the front of this list (which is the top of the
	 *         stack represented by this list)
	 * @throws NoSuchElementException
	 *             if this list is empty
	 * @since 1.6
	 */
	public E pop() {
		return removeFirst();
	}

	// pop() push(E e)
	// 这两个方法对应栈的操作，即弹出一个元素和压入一个元素，仅仅是调用了removeFirst()和addFirst()方法。
	/**
	 * Removes the first occurrence of the specified element in this list (when
	 * traversing the list from head to tail). If the list does not contain the
	 * element, it is unchanged.
	 * 
	 * @param o
	 *            element to be removed from this list, if present
	 * @return <tt>true</tt> if the list contained the specified element
	 * @since 1.6
	 */
	public boolean removeFirstOccurrence(Object o) {
		return remove(o);
	}

	/**
	 * Removes the last occurrence of the specified element in this list (when
	 * traversing the list from head to tail). If the list does not contain the
	 * element, it is unchanged.
	 * 
	 * @param o
	 *            element to be removed from this list, if present
	 * @return <tt>true</tt> if the list contained the specified element
	 * @since 1.6
	 */
	public boolean removeLastOccurrence(Object o) {
		if (o == null) {
			for (Entry<E> e = header.previous; e != header; e = e.previous) {
				if (e.element == null) {
					remove(e);
					return true;
				}
			}
		} else {
			for (Entry<E> e = header.previous; e != header; e = e.previous) {
				if (o.equals(e.element)) {
					remove(e);
					return true;
				}
			}
		}
		return false;
	}

	/**
	 * Returns a list-iterator of the elements in this list (in proper
	 * sequence), starting at the specified position in the list. Obeys the
	 * general contract of <tt>List.listIterator(int)</tt>.
	 * <p>
	 * 
	 * The list-iterator is <i>fail-fast</i>: if the list is structurally
	 * modified at any time after the Iterator is created, in any way except
	 * through the list-iterator's own <tt>remove</tt> or <tt>add</tt> methods,
	 * the list-iterator will throw a <tt>ConcurrentModificationException</tt>.
	 * Thus, in the face of concurrent modification, the iterator fails quickly
	 * and cleanly, rather than risking arbitrary, non-deterministic behavior at
	 * an undetermined time in the future.
	 * 
	 * @param index
	 *            index of the first element to be returned from the
	 *            list-iterator (by a call to <tt>next</tt>)
	 * @return a ListIterator of the elements in this list (in proper sequence),
	 *         starting at the specified position in the list
	 * @throws IndexOutOfBoundsException
	 *             {@inheritDoc}
	 * @see List#listIterator(int)
	 */
	public ListIterator<E> listIterator(int index) {
		return new ListItr(index);
	}

	/*
	 * 除了Entry，LinkedList还有一个内部类：ListItr。
	 * ListItr实现了ListIterator接口，可知它是一个迭代器，通过它可以遍历修改LinkedList。
	 * 在LinkedList中提供了获取ListItr对象的方法：listIterator(int index)
	 */
	private class ListItr implements ListIterator<E> {
		// 最近一次返回的节点，也是当前持有的节点
		private Entry<E> lastReturned = header;
		// 对下一个元素的引用
		private Entry<E> next;
		// 下一个节点的index
		private int nextIndex;
		private int expectedModCount = modCount;

		// 构造方法，接收一个index参数
		ListItr(int index) {
			// 如果index小于0或大于size，抛出IndexOutOfBoundsException异常
			if (index < 0 || index > size)
				throw new IndexOutOfBoundsException("Index: " + index
						+ ", Size: " + size);

			// 判断遍历方向
			if (index < (size >> 1)) {
				// next赋值为第一个节点
				next = header.next;
				// 获取指定位置的节点
				for (nextIndex = 0; nextIndex < index; nextIndex++)
					next = next.next;
			} else {
				// else中的处理和if块中的处理一致，只是遍历方向不同
				next = header;
				for (nextIndex = size; nextIndex > index; nextIndex--)
					next = next.previous;
			}
		}

		// 根据nextIndex是否等于size判断时候还有下一个节点（也可以理解为是否遍历完了LinkedList）
		public boolean hasNext() {
			return nextIndex != size;
		}

		// 获取下一个元素
		public E next() {
			checkForComodification();
			// 如果nextIndex==size,则已经遍历完链表，即没有下一个节点了
			// （实际上是有的，因为是循环链表，任何一个节点都会有上一个和下一个节点，这里的没有下一个节点只是说所有节点都已经遍历完了）
			if (nextIndex == size)
				throw new NoSuchElementException();

			// 设置最近一次返回的节点为next节点
			lastReturned = next;
			// 将next“向后移动一位”
			next = next.next;
			// index计数加1
			nextIndex++;
			// 返回lastReturned的元素
			return lastReturned.element;
		}

		public boolean hasPrevious() {
			return nextIndex != 0;
		}

		// 返回上一个节点，和next()方法相似
		public E previous() {
			if (nextIndex == 0)
				throw new NoSuchElementException();

			lastReturned = next = next.previous;
			nextIndex--;
			checkForComodification();
			return lastReturned.element;
		}

		public int nextIndex() {
			return nextIndex;
		}

		public int previousIndex() {
			return nextIndex - 1;
		}

		// 移除当前Iterator持有的节点
		public void remove() {
			checkForComodification();
			Entry<E> lastNext = lastReturned.next;
			try {
				LinkedList.this.remove(lastReturned);
			} catch (NoSuchElementException e) {
				throw new IllegalStateException();
			}
			if (next == lastReturned)
				next = lastNext;
			else
				nextIndex--;
			lastReturned = header;
			expectedModCount++;
		}

		// 修改当前节点的内容
		public void set(E e) {
			if (lastReturned == header)
				throw new IllegalStateException();
			checkForComodification();
			lastReturned.element = e;
		}

		// 在当前持有节点后面插入新节点
		public void add(E e) {
			checkForComodification();
			lastReturned = header;
			addBefore(e, next);
			nextIndex++;
			expectedModCount++;
		}

		// 判断expectedModCount和modCount是否一致，以确保通过ListItr的修改操作正确的反映在LinkedList中
		final void checkForComodification() {
			if (modCount != expectedModCount)
				throw new ConcurrentModificationException();
		}
	}

	// 只定义了存储的元素、前一个元素、后一个元素，这就是双向链表的节点的定义，每个节点只知道自己的前一个节点和后一个节点。
	private static class Entry<E> {
		E element;
		Entry<E> next;
		Entry<E> previous;

		Entry(E element, Entry<E> next, Entry<E> previous) {
			this.element = element;
			this.next = next;
			this.previous = previous;
		}
	}

	// addBefore(E e,Entry<E>
	// entry)方法是个私有方法，所以无法在外部程序中调用（当然，这是一般情况，你可以通过反射上面的还是能调用到的）。
	/*
	 * addBefore(E e,Entry<E>
	 * entry)先通过Entry的构造方法创建e的节点newEntry（包含了将其下一个节点设置为entry，
	 * 上一个节点设置为entry.previous的操作，相当于修改newEntry的“指针”），
	 * 之后修改插入位置后newEntry的前一节点的next引用和后一节点的previous引用，使链表节点间的引用关系保持正确。
	 * 之后修改和size大小和记录modCount，然后返回新插入的节点。
	 * 
	 * 总结，addBefore(E e,Entry<E> entry)实现在entry之前插入由e构造的新节点。而add(E
	 * e)实现在header节点之前插入由e构造的新节点。
	 */
	private Entry<E> addBefore(E e, Entry<E> entry) {
		Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
		newEntry.previous.next = newEntry;
		newEntry.next.previous = newEntry;
		size++;
		modCount++;
		return newEntry;
	}

	// 几个remove方法最终都是调用了一个私有方法：remove(Entry<E> e)，只是其他简单逻辑上的区别。
	// 下面分析remove(Entry<E> e)方法。
	private E remove(Entry<E> e) {
		if (e == header)
			throw new NoSuchElementException();

		// 保留将被移除的节点e的内容
		E result = e.element;
		// 将前一节点的next引用赋值为e的下一节点
		e.previous.next = e.next;
		// 将e的下一节点的previous赋值为e的上一节点
		e.next.previous = e.previous;
		// 上面两条语句的执行已经导致了无法在链表中访问到e节点，而下面解除了e节点对前后节点的引用
		e.next = e.previous = null;
		// 将被移除的节点的内容设为null
		e.element = null;
		// 修改size大小
		size--;
		modCount++;
		// 返回移除节点e的内容
		return result;
	}

	/**
	 * @since 1.6
	 */
	// LinkedList还有一个提供Iterator的方法：descendingIterator()。该方法返回一个DescendingIterator对象。
	// DescendingIterator是LinkedList的一个内部类。
	public Iterator<E> descendingIterator() {
		return new DescendingIterator();
	}

	/** Adapter to provide descending iterators via ListItr.previous */
	// 从类名和上面的代码可以看出这是一个反向的Iterator，代码很简单，都是调用的ListItr类中的方法。
	private class DescendingIterator implements Iterator {
		// 获取ListItr对象
		final ListItr itr = new ListItr(size());

		// hasNext其实是调用了itr的hasPrevious方法
		public boolean hasNext() {
			return itr.hasPrevious();
		}

		// next()其实是调用了itr的previous方
		public E next() {
			return itr.previous();
		}

		public void remove() {
			itr.remove();
		}
	}

	/**
	 * Returns a shallow copy of this <tt>LinkedList</tt>. (The elements
	 * themselves are not cloned.)
	 * 
	 * @return a shallow copy of this <tt>LinkedList</tt> instance
	 */
	/*
	 * 调用父类的clone()方法初始化对象链表clone，将clone构造成一个空的双向循环链表，
	 * 之后将header的下一个节点开始将逐个节点添加到clone中。最后返回克隆的clone对象。
	 */
	public Object clone() {
		LinkedList<E> clone = null;
		try {
			clone = (LinkedList<E>) super.clone();
		} catch (CloneNotSupportedException e) {
			throw new InternalError();
		}

		// Put clone into "virgin" state
		clone.header = new Entry<E>(null, null, null);
		clone.header.next = clone.header.previous = clone.header;
		clone.size = 0;
		clone.modCount = 0;

		// Initialize clone with our elements
		for (Entry<E> e = header.next; e != header; e = e.next)
			clone.add(e.element);

		return clone;
	}

	/**
	 * Returns an array containing all of the elements in this list in proper
	 * sequence (from first to last element).
	 * 
	 * <p>
	 * The returned array will be "safe" in that no references to it are
	 * maintained by this list. (In other words, this method must allocate a new
	 * array). The caller is thus free to modify the returned array.
	 * 
	 * <p>
	 * This method acts as bridge between array-based and collection-based APIs.
	 * 
	 * @return an array containing all of the elements in this list in proper
	 *         sequence
	 */
	// 创建大小和LinkedList相等的数组result，遍历链表，将每个节点的元素element复制到数组中，返回数组。
	public Object[] toArray() {
		Object[] result = new Object[size];
		int i = 0;
		for (Entry<E> e = header.next; e != header; e = e.next)
			result[i++] = e.element;
		return result;
	}

	/**
	 * Returns an array containing all of the elements in this list in proper
	 * sequence (from first to last element); the runtime type of the returned
	 * array is that of the specified array. If the list fits in the specified
	 * array, it is returned therein. Otherwise, a new array is allocated with
	 * the runtime type of the specified array and the size of this list.
	 * 
	 * <p>
	 * If the list fits in the specified array with room to spare (i.e., the
	 * array has more elements than the list), the element in the array
	 * immediately following the end of the list is set to <tt>null</tt>. (This
	 * is useful in determining the length of the list <i>only</i> if the caller
	 * knows that the list does not contain any null elements.)
	 * 
	 * <p>
	 * Like the {@link #toArray()} method, this method acts as bridge between
	 * array-based and collection-based APIs. Further, this method allows
	 * precise control over the runtime type of the output array, and may, under
	 * certain circumstances, be used to save allocation costs.
	 * 
	 * <p>
	 * Suppose <tt>x</tt> is a list known to contain only strings. The following
	 * code can be used to dump the list into a newly allocated array of
	 * <tt>String</tt>:
	 * 
	 * <pre>
	 * String[] y = x.toArray(new String[0]);
	 * </pre>
	 * 
	 * Note that <tt>toArray(new Object[0])</tt> is identical in function to
	 * <tt>toArray()</tt>.
	 * 
	 * @param a
	 *            the array into which the elements of the list are to be
	 *            stored, if it is big enough; otherwise, a new array of the
	 *            same runtime type is allocated for this purpose.
	 * @return an array containing the elements of the list
	 * @throws ArrayStoreException
	 *             if the runtime type of the specified array is not a supertype
	 *             of the runtime type of every element in this list
	 * @throws NullPointerException
	 *             if the specified array is null
	 */
	/*
	 * 先判断出入的数组a的大小是否足够，若大小不够则拓展。这里用到了发射的方法，
	 * 重新实例化了一个大小为size的数组。之后将数组a赋值给数组result，遍历链表向result中添加的元素。
	 * 最后判断数组a的长度是否大于size，若大于则将size位置的内容设置为null。返回a。
	 * 
	 * 从代码中可以看出，数组a的length小于等于size时，a中所有元素被覆盖，被拓展来的空间存储的内容都是null；
	 * 若数组a的length的length大于size，则0至size-1位置的内容被覆盖，size位置的元素被设置为null，size之后的元素不变。
	 */
	public <T> T[] toArray(T[] a) {
		if (a.length < size)
			a = (T[]) java.lang.reflect.Array.newInstance(a.getClass()
					.getComponentType(), size);
		int i = 0;
		// 为什么不直接对数组a进行操作，要将a赋值给result数组之后对result数组进行操作？
		Object[] result = a;
		for (Entry<E> e = header.next; e != header; e = e.next)
			result[i++] = e.element;

		if (a.length > size)
			a[size] = null;

		return a;
	}

	private static final long serialVersionUID = 876323262645176354L;

	/**
	 * Save the state of this <tt>LinkedList</tt> instance to a stream (that is,
	 * serialize it).
	 * 
	 * @serialData The size of the list (the number of elements it contains) is
	 *             emitted (int), followed by all of its elements (each an
	 *             Object) in the proper order.
	 */
	private void writeObject(java.io.ObjectOutputStream s)
			throws java.io.IOException {
		// Write out any hidden serialization magic
		s.defaultWriteObject();

		// Write out size
		s.writeInt(size);

		// Write out all elements in the proper order.
		for (Entry e = header.next; e != header; e = e.next)
			s.writeObject(e.element);
	}

	/**
	 * Reconstitute this <tt>LinkedList</tt> instance from a stream (that is
	 * deserialize it).
	 */
	private void readObject(java.io.ObjectInputStream s)
			throws java.io.IOException, ClassNotFoundException {
		// Read in any hidden serialization magic
		s.defaultReadObject();

		// Read in size
		int size = s.readInt();

		// Initialize header
		header = new Entry<E>(null, null, null);
		header.next = header.previous = header;

		// Read in all elements in the proper order.
		for (int i = 0; i < size; i++)
			addBefore((E) s.readObject(), header);
	}
}
